UVa/107 - The Cat in the Hat/main.cpp

   1 #include <cstdlib>
   2 #include <iostream>
   3
   4 using namespace std;
   5
   6 /*
   7 The Cat in the Hat
   8 Problema 107 de la ACM
   9 por Andrés Mejía
  10
  11 http://acm.uva.es/p/v1/107.html
  12
  13 Fecha: 26/Febrero/2007
  14
  15 GT = Gatos trabajadores
  16 GNT = Gatos no trabajadores
  17 */
  18
  19 bool isValidN(const int &N, const int &filas, const int &alturaGatoInicial){
  20      int tempAltura = alturaGatoInicial;
  21      for (int i=0; i < (filas-1); i++){
  22          if (tempAltura % (N + 1) != 0) return false; //si no es divisible retorna falso
  23          tempAltura /= (N + 1);
  24      }
  25      if (tempAltura == 1)
  26          return true;
  27      else
  28          return false;
  29 }
  30
  31 int encontrarN(const int &numeroGatosTrabajadores, const int &alturaGatoInicial, int &SetFilas){
  32     //if (numeroGatosTrabajadores == 1) return 1;
  33     int posible = 1;
  34     int temp, filas;
  35     while (posible <= numeroGatosTrabajadores){
  36           temp = 1; filas = 1;
  37           while (temp < numeroGatosTrabajadores){
  38                 temp = temp * posible;
  39                 filas += 1;
  40           }
  41
  42           //cout << "filas: " << filas << endl;
  43
  44           if (temp == numeroGatosTrabajadores){
  45                    if (isValidN(posible, filas, alturaGatoInicial)){
  46                        SetFilas = filas;
  47                        return posible;
  48                        }
  49           }
  50           posible += 1;
  51     }
  52     return 0; //En teoria nunca debería pasar
  53 }
  54
  55 int potenciar(const int &base, const int &exponente){
  56         int result = 1;
  57         for (int i=0; i<exponente; i++) {
  58             result = result * base;
  59         }
  60         return result;
  61 }
  62
  63 int getGNT(const int &N, const int &filas){
  64     int result = 1;
  65     if (filas == 1) return 0;
  66     for (int i=1; i<(filas-1); i++){
  67         result += potenciar(N, i);
  68     }
  69     return result;
  70 }
  71
  72 int getSumaAlturas(const int &N, const int &filas, int alturaPrimerGato){
  73
  74     int suma = alturaPrimerGato;
  75
  76     for (int i=1; i<filas; i++){
  77         alturaPrimerGato /= (N+1);
  78         suma += potenciar(N, i) * alturaPrimerGato;
  79     }
  80     return suma;
  81 }
  82
  83
  84 int main(int argc, char *argv[])
  85 {
  86     int alturaPrimerGato;
  87     int numeroGT;
  88     int filas;
  89     int N;
  90
  91     while (cin >> alturaPrimerGato && cin >> numeroGT){
  92           if (alturaPrimerGato == 0 && numeroGT == 0) break;
  93           filas = 0;
  94           //cout << "N: " << encontrarN(numeroGT, alturaPrimerGato, filas) << endl;
  95           //cout << "filas: " << filas << endl;
  96           N = encontrarN(numeroGT, alturaPrimerGato, filas);
  97           cout << getGNT(N, filas) << " " << getSumaAlturas(N, filas, alturaPrimerGato) << endl;
  98     }
  99     return 0;
 100 }